package org.example.dataStructure.linkedList;

/**
 * @author yuwl
 * @description 链表实现 LRU（最近最少使用）缓存
 * 实现LRU缓存的一种常见方法是使用双向链表和哈希表的结合。双向链表用于维护缓存中的元素顺序，哈希表用于快速查找缓存中是否存在某个元素。以下是用Java实现LRU缓存的基本思路：
 * 1.创建一个双向链表，链表中的每个节点包含键值对。
 * 2.创建一个哈希表，用于将键映射到链表中的节点。
 * 3.当要获取某个键对应的值时，先在哈希表中查找是否存在该键，如果存在，则将对应的节点移到链表头部，并返回该节点的值。
 * 4.当要插入一个新的键值对时，先在哈希表中查找是否存在该键，如果存在，则更新对应节点的值，并将该节点移到链表头部；如果不存在，则创建一个新节点，并将其插入到链表头部，并在哈希表中添加该键值对。
 * 5.当缓存达到最大容量时，删除链表尾部节点，并在哈希表中移除对应的键。
 *
 * 在实现LRU缓存时选择双向链表而不是单向链表的原因有几点：
 * 1.快速删除节点：双向链表可以快速删除任意节点，而单向链表删除节点时需要找到该节点的前驱节点，这需要顺序遍历链表，时间复杂度为O(n)，而双向链表的删除操作只需要O(1)的时间复杂度。
 * 2.快速更新节点位置：当访问一个节点时，我们需要将该节点移到链表头部，双向链表可以在O(1)时间内完成这个操作，而单向链表则需要从头遍历找到该节点的前驱节点，时间复杂度为O(n)。
 * 3.实现简单：双向链表相对于单向链表来说，实现起来更加简单。在单向链表中，为了删除节点，我们需要记录前驱节点，而在双向链表中，每个节点都可以直接访问到它的前驱节点，这样操作起来更加方便。
 * @since 2024-05-22 11:22
 */
import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    // 定义节点类
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 缓存容量
    private int capacity;
    // 哈希表，用于快速查找节点
    private Map<Integer, Node> map;
    // 双向链表的头节点和尾节点
    private Node head;
    private Node tail;

    // 构造函数，初始化LRU缓存
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        // 初始化头节点和尾节点
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    // 获取缓存中某个键对应的值
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 将访问的节点移到链表头部
            removeNode(node);
            addNodeToHead(node);
            return node.value;
        }
        return -1;
    }

    // 插入新的键值对
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            // 将访问的节点移到链表头部
            removeNode(node);
            addNodeToHead(node);
        } else {
            // 如果缓存已满，移除链表尾部节点
            if (map.size() == capacity) {
                Node tailNode = tail.prev;
                removeNode(tailNode);
                map.remove(tailNode.key);
            }
            // 创建新节点并插入到链表头部
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addNodeToHead(newNode);
        }
    }

    // 删除节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将节点插入到链表头部
    private void addNodeToHead(Node node) {
        node.next = head.next;
        node.next.prev = node;
        node.prev = head;
        head.next = node;
    }

    public static void main(String[] args) {
        // 测试LRU缓存容量为2
        LRUCache cache = new LRUCache(2);

        // 添加键值对
        cache.put(1, 1);
        cache.put(2, 2);

        // 此时缓存状态为：(2, 2) <-> (1, 1)
        // 获取键1对应的值，返回1，此时缓存状态不变
        System.out.println(cache.get(1)); // Output: 1

        // 此时缓存状态为：(1, 1) <-> (2, 2)
        // 添加新键值对，缓存容量已满，移除最近最少使用的键值对(2, 2)
        cache.put(3, 3);

        // 此时缓存状态为：(3, 3) <-> (1, 1)
        // 获取键2对应的值，键不存在于缓存中，返回-1
        System.out.println(cache.get(2)); // Output: -1

        // 此时缓存状态为：(3, 3) <-> (1, 1)
        // 添加新键值对，缓存容量已满，移除最近最少使用的键值对(1, 1)
        cache.put(4, 4);

        // 此时缓存状态为：(4, 4) <-> (3, 3)
        // 获取键1对应的值，键不存在于缓存中，返回-1
        System.out.println(cache.get(1)); // Output: -1

        // 获取键3对应的值，返回3，此时缓存状态不变
        System.out.println(cache.get(3)); // Output: 3

        // 此时缓存状态为：(3, 3) <-> (4, 4)
        // 获取键4对应的值，返回4，此时缓存状态不变
        System.out.println(cache.get(4)); // Output: 4
    }
}


